package lecode01;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class 全排列46 {

    public static void main(String[] args) {
       int[] nums =  {1,2,3};
//        List<List<Integer>> permute = permute(nums);
        List<List<Integer>> lists = permute(nums);
//        System.out.println(permute);
        System.out.println(lists);
    }

    /**
     * 回溯算法 （递归）
     *
     */
    public static List<List<Integer>> permute(int[] nums) {
        //结果
        List<List<Integer>> result = new ArrayList<>();
        //先排序
        List<Integer> origin = Arrays.stream(nums).boxed().sorted().collect(Collectors.toList());
        //将每个原始元素做上标记
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (Integer value : origin) {
            map.put(value, false);
        }
        //拼接目标数组
        backtracking(origin,result,map,new ArrayList<Integer>());
        return result;
    }

    /**
     * 递归
     * @param origins 原始数组
     * @param result 最终结果数组
     * @param hash   判断元素是否出现过
     * @param tagList   拼接的数组
     */
    public static void backtracking(List<Integer> origins, List<List<Integer>> result, HashMap<Integer,Boolean> hash,List<Integer> tagList) {
        //结束条件 如果当前拼接的tagList的长度与原始数组长度一样就说明拼接了一个有效的数组
        if (origins.size() == tagList.size()) {
            //讲结果复制到结果集
            result.add(new ArrayList<>(tagList));
            return;
        }
        //判断当前元素是否已经使用过
        for (Integer origin : origins) {
            //没有使用过，做拼接
            if (!hash.get(origin)) {
                hash.put(origin, true);
                tagList.add(origin);
                backtracking(origins, result, hash, tagList);
                //重置判断状态和零时tagList
                hash.put(origin, false);
                tagList.remove(tagList.size() - 1);
            }
        }

    }



    /**
     * 方法二、用数组做标识
     *
     */
    static List<Integer> path = new ArrayList<>();
    static List<List<Integer>> res = new ArrayList<>();
    static boolean[] used; //0为false
    public static List<List<Integer>> permute2(int[] nums) {
        used = new boolean[nums.length];//使用标记数组，避免重复使用。以空间换时间
        System.out.println("used " + Arrays.toString(used));
        permuteHelper(nums);
        return res;
    }

    public static void permuteHelper(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length ; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }

}
